#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

typedef struct
{
    int* a;
    int capacity;
    int top;
} Stack;


typedef struct
{
    Stack s1;
    Stack s2;
} MyQueue;

void StackInit(Stack* s)
{
    assert(s);

    s->a = (int*)malloc(sizeof(int) * 3);
    if (s->a == NULL)
    {
        perror("malloc fail");
        return;
    }

    s->capacity = 3;
    s->top = 0;
}

void StackPush(Stack* s, int x)
{
    assert(s);

    if (s->top == s->capacity)
    {
        int* tmp = realloc(s->a, sizeof(int) * (s->capacity + 2));
        if (tmp == NULL)
        {
            perror("realloc fail");
            return;
        }

        s->a = tmp;
        s->capacity += 2;
    }

    s->a[s->top] = x;
    s->top++;
}

void StackPop(Stack* s)
{
    assert(s);
    assert(s->top);

    s->top--;
}

void StackDestroy(Stack* s)
{
    assert(s);

    free(s->a);
    s->a = NULL;

    s->capacity = 0;
    s->top = 0;

}
MyQueue* myQueueCreate()
{
    MyQueue* Q = (MyQueue*)malloc(sizeof(MyQueue));
    if (Q == NULL)
    {
        perror("malloc fail");
        return NULL;
    }

    StackInit(&(Q->s1));
    StackInit(&(Q->s2));

    return Q;
}

void myQueuePush(MyQueue* obj, int x)
{
    assert(obj);

    if (obj->s1.top != 0)
    {
        StackPush(&(obj->s1), x);
    }
    else
    {
        StackPush(&(obj->s2), x);
    }
}

int myQueuePop(MyQueue* obj)
{
    assert(obj);

    if (obj->s1.top != 0)
    {
        while (obj->s1.top)
        {
            StackPush(&(obj->s2), obj->s1.a[obj->s1.top - 1]);
            StackPop(&(obj->s1));
        }
        int top = obj->s2.a[obj->s2.top - 1];
        StackPop(&(obj->s2));
        return top;
    }
    else
    {
        while (obj->s2.top)
        {
            StackPush(&(obj->s1), obj->s2.a[obj->s2.top - 1]);
            StackPop(&(obj->s2));
        }
        int top = obj->s1.a[obj->s1.top - 1];
        StackPop(&(obj->s1));
        return top;
    }
}

int myQueuePeek(MyQueue* obj)
{
    assert(obj);

    if (obj->s1.top != 0)
    {
        return obj->s1.a[0];
    }
    else
    {
        return obj->s2.a[0];
    }
}

bool myQueueEmpty(MyQueue* obj)
{
    assert(obj);

    return (obj->s1.top == 0) && (obj->s2.top == 0);
}

void myQueueFree(MyQueue* obj)
{
    assert(obj);

    StackDestroy(&(obj->s1));
    StackDestroy(&(obj->s2));

    free(obj);
    obj = NULL;
}

/**
 * Your MyQueue struct will be instantiated and called as such:
 * MyQueue* obj = myQueueCreate();
 * myQueuePush(obj, x);

 * int param_2 = myQueuePop(obj);

 * int param_3 = myQueuePeek(obj);

 * bool param_4 = myQueueEmpty(obj);

 * myQueueFree(obj);
*/
int main()
{
    MyQueue* q = myQueueCreate();

    myQueuePush(q, 1);
    myQueuePush(q, 2);
    myQueuePop(q);

    return 0;
}